class DSU:
def __init__(self,n,arr):
self.rank = [0 for _ in range(n)]
self.parent = [i for i in range(n)]
self.sum = [arr[i] for i in range(n)]
def max_sum(self,par2,par1):
self.sum[par1]+=self.sum[par2]
return self.sum[par1]
def find(self,x):
if self.parent[x]!=x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self,x,y):
par1 = self.find(x)
par2 = self.find(y)
if par1==par2:
return
if self.rank[par1]>self.rank[par2]:
out = self.max_sum(par2,par1)
self.parent[par2] = par1
else:
out = self.max_sum(par1, par2)
self.parent[par1] = par2
if self.rank[par1] ==self.rank[par2]:
self.rank[par2]+=1
return out
def destroy(N,L,index):
dsu_obj = DSU(N,L)
place_fill = [False for _ in range(N)]
output = [0]
max_sum = 0
for val in index[:0:-1]:
id = val-1
comp_sum = L[id]
place_fill[id] = True
if id-1>=0 and place_fill[id-1]:
comp_sum = dsu_obj.union(id-1,id)
if id+1<N and place_fill[id+1]:
comp_sum = dsu_obj.union(id,id+1)
if comp_sum>max_sum:
max_sum = comp_sum
output.append(max_sum)
for val in output[::-1]:
print(val)
N = int(input())
L = list(map(int,input().split()))
index = list(map(int,input().split()))
destroy(N,L,index)
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
typedef long long ll ;
#define lup(i,a,b) for (int i=(a) ; i<(b) ; i++)
#define ld(i,a,b) for (int i=(a) ; i>=(b) ; i--)
ll mod=1e9+7 ;
ll po(ll n,ll m, ll mod )
{
if(!m)
return 1 ;
if(m%2==0)
{
ll c=po(n,m/2,mod) ;
c%=mod ;
return (c*c)%mod ;
}
else
{
ll y=n%mod ;
return (y*(po(n,m-1,mod)%mod))%mod ;
}
}
const int N=1e5+5, M=1e5+6 ;
int n, m, ne, head[N], nxt[M], to[M] ;
void initgraph()
{
memset(head,-1,n*sizeof head[0]) ;
}
void adedge (int f, int t)
{
to[ne]=t ;
nxt[ne]=head[f] ;
head[f]=ne++ ;
}
void adbiedge(int u, int v)
{
adedge(u,v) ;
adedge(v,u) ;
}
double eps=1e-7 ;
int dx[4]= {-1,0,1,0} ;
int dy[4]= {0,1,0,-1} ;
bool valid(int i,int j,int n,int m)
{
return (i>=0 && i<=1+n && j>=0 && j<=1+m ) ;
}
ll p[300009] , sum[200000];
int findparent(int u)
{
if(p[u]==u) return u ;
return p[u]=findparent(p[u]) ;
}
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
//freopen("input.txt","r",stdin) ;
//freopen("output.txt","w",stdout) ;
// cout << fixed << setprecision(3) ;
int n , u ,ve ;
cin >> n ;
vector<ll>v(n+1) , a(n+1) , ans(n+1);
lup(i,1,n+1) p[i]=i ;
lup(i,1,n+1) { cin >> a[i] ; sum[i]=a[i] ; }
lup(i,1,n+1) cin >> v[i] ;
ll mx=0 ;
int f[n+2]={0} ;
ld(i,n,1)
{
ans[i]=mx ;
int x=v[i] ;
f[x]++ ;
if(f[x-1] && !f[x+1])
{
u=findparent(x-1) ;
sum[u]+=sum[x] ;
p[x]=u ;
}
else if(f[x+1] && !f[x-1])
{
u=findparent(x+1) ;
sum[u]+=sum[x] ;
p[x]=u ;
}
else if(f[x-1] && f[x+1])
{
u=findparent(x+1) , ve=findparent(x-1) ;
sum[u]+=(sum[x]+sum[ve]) ;
p[ve]=u , p[x]=u ;
}
mx=max(mx,sum[findparent(x)]) ;
}
lup(i,1,n+1) cout << ans[i] << "\n" ;
}
380. Insert Delete GetRandom O(1) | 332. Reconstruct Itinerary |
368. Largest Divisible Subset | 377. Combination Sum IV |
322. Coin Change | 307. Range Sum Query - Mutable |
287. Find the Duplicate Number | 279. Perfect Squares |
275. H-Index II | 274. H-Index |
260. Single Number III | 240. Search a 2D Matrix II |
238. Product of Array Except Self | 229. Majority Element II |
222. Count Complete Tree Nodes | 215. Kth Largest Element in an Array |
198. House Robber | 153. Find Minimum in Rotated Sorted Array |
150. Evaluate Reverse Polish Notation | 144. Binary Tree Preorder Traversal |
137. Single Number II | 130. Surrounded Regions |
129. Sum Root to Leaf Numbers | 120. Triangle |
102. Binary Tree Level Order Traversal | 96. Unique Binary Search Trees |
75. Sort Colors | 74. Search a 2D Matrix |
71. Simplify Path | 62. Unique Paths |